Mesh networking is a type of networking wherein each node in the network may act as an independent router, regardless of whether it is connected to another network or not. Mesh networks may be implemented with any number of computing entities. For example, several wireless computing devices, such as mobile smart phones, may form a mesh network. As another example, several processing components on a single integrated circuit (IC) chip or multiple ICs may form a mesh network. Such a mesh network, with multiples processing nodes and paths between nodes allows for continuous connections and reconfiguration around broken or blocked paths by using different paths for data transfer from node to node. A mesh network whose nodes are all connected to each other is a fully connected network.
One particular aspect of mesh networking has been implemented in ICs that are categorized as Very Large Scale Integration (VLSI) chips. In these ICs, a two-dimensional (2D) mesh of processing nodes may be realized on a single flat IC chip. Such multiprocessor ICs are becoming more widely utilized to efficiently use the increasing number of transistors available in modern VLSI technology. As the number of processing nodes increases, an on-chip network (i.e., a 2D mesh network) is implemented to facilitate communications and data transfer between the various processing nodes. The overall schema for facilitating this communication and data transfer is referred to as a routing algorithm or simply routing. Conventional routing for a 2D mesh network on an IC provides a very simple grid-like network which may result in short connections within the chip architecture. However, problems abound when multiple communication and data transfer paths are formed. As one node may need to broadcast data to several nodes, conventional routing algorithms are inefficient and cumbersome because some data may be duplicated in concurrent paths or parallel divergent paths even though shorter and more efficient routes may be available.